package 链表;

import java.util.Stack;

import static 链表.一_反转链表.printListNode;

/**
 * @Author Weton Li
 * @Date 2021/3/14 19:57
 */
public class 三_删除链表倒数第n个节点 {

    public static ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode sentinel = new ListNode(-1);
        sentinel.next = head;
        // 定义栈
        Stack<ListNode> stack = new Stack<>();
        ListNode curr = sentinel;
        // 遍历链表，所有节点入栈
        while (curr != null) {
            stack.push(curr);
            curr = curr.next;
        }
        // 依次弹栈，弹出N个
        for (int i = 0; i < n; i++) {
            ListNode pop = stack.pop();
            System.out.println("pop()出的元素为：" + pop.value);
        }
        ListNode peek = stack.peek();
        System.out.println("窥探栈顶元素：" + peek.value);
        System.out.println(peek.next.value);
        stack.peek().next = stack.peek().next.next;
        return sentinel.next;
    }

    public static ListNode removeNthFromEnd2(ListNode head, int n) {

        // 1.获取链表长度。
        int length = getListLength(head);
        // 2.防止特殊情况直接删除倒数第n个结点（头结点），定义哨兵节点。定义当前节点，初始指向哨兵节点
        ListNode sentinel = new ListNode(head, -1);
        ListNode curr = sentinel;
        // 3.遍历l-n次，找到待删除元素的前一个元素，它的下一个元素=下下一个元素
        for (int i = 0; i < length - n; i++) {
            curr = curr.next;
        }
        curr.next = curr.next.next;
        // 返回的是哨兵节点的下一个节点
        return sentinel.next;
    }

    /**
     * 举例 1->3->5->7->9->null
     * @param head 初始为哨兵节点-1
     * @param n 为3
     * @return 返回哨兵节点的下一个节点
     */
    public static ListNode removeNthFromEnd(ListNode head,int n){
        // 1.定义哨兵节点。定义前后节点，初始在哨兵节点处。
        ListNode sentinel = new ListNode(head, -1);
        ListNode first = sentinel,second = sentinel;
        sentinel.next = head; // 勿忘连接哨兵节点的下一个节点为头结点
        // 2.为了保证后指针最终指到待删除元素的前一个节点，举例中后指针至少需要移动2步。
        //   从null往前推2步，即前指针必须 事先 移动到7位置（必须走4步即n+1步），此时前指针再向后移动2位即为null.
        //   此为while循环的退出条件。
        for (int i = 0; i < n + 1; i++) {
            first = first.next;
        }

        while (first != null) {
            first = first.next;
            second = second.next;
        }

        second.next = second.next.next;
        // 返回哨兵节点的下一个节点为头结点
        return sentinel.next;
    }

    public static int getListLength(ListNode head) {

        ListNode curr = head;
        int length = 0;
        while (curr != null) {
            length++;
            curr = curr.next;
        }
        return length;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2; // 使两节点相连接
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        listNode5.next = null;

        printListNode(listNode1);

        removeNthFromEnd(listNode1, 2);

        printListNode(listNode1);
    }
}
